/**
 * 分治法，最大的子数组总是左边的最大子数组和中间往两边的最大子数组以及右边最大子数组，里面最大的一个
 * 然后一层层递归
 * 复杂度 大概是 n*logn
 *
 * @param array arr 要求的数组
 * @param int  left 开始的坐标
 * @param int  right 结束的坐标
 * @return obj 返回结果对象
 * */
function divide(arr,left,right) {
    var maxleft=0,maxright=0;
    var maxleftmiddle=0,maxrightmiddle=0,leftmiddlesum=0,rightmiddlesum=0;
    var center,max=0;
    if(left==right){
        return{
            max:arr[left],
            start:left,
            end:left,
            subarr:arr.slice(left,left+1)
        } ;
    }else{

        center = Math.floor((left+right)/2) ; //中间数向下取整
        maxleft=divide(arr,left,center);//左边最大
        maxright=divide(arr,center+1,right);//右边最大

        var start=center,end=center;
        for(var i=center;i>=left;i--){//从中间到左的最大
            leftmiddlesum+=arr[i];
            if(maxleftmiddle<leftmiddlesum){
                maxleftmiddle = leftmiddlesum;
                start=i;

            }
        }

        for(var j=center+1;j<=right;j++){//从中间到右边的最大
            rightmiddlesum+=arr[j];
            if(maxrightmiddle<rightmiddlesum){
                maxrightmiddle = rightmiddlesum;
                end=j;

            }
        }


        if(maxleft.max>maxright.max){ // 两边比较大小
            startlr = maxleft.start;
            endlr = maxleft.end;
            max = maxleft.max;
        }else{
            startlr = maxright.start;
            endlr = maxright.end;
            max = maxright.max;
        }

        if( max < (maxleftmiddle+maxrightmiddle) ){//中间大
            max = (maxleftmiddle+maxrightmiddle);
        }else{//两边大
            start = startlr;
            end = endlr;
        }

        return {
            max:max,
            start:start,
            end:end,
            subarr:arr.slice(start,end+1)
        } ;

    }

}

// console.log(divide(arr,0,arr.length-1));
exports.divide = divide;